﻿// 089. a^b.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;


/*

https://www.acwing.com/problem/content/91/

求 a 的 b 次方对 p 取模的值。

输入格式
三个整数 a,b,p ,在同一行用空格隔开。

输出格式
输出一个整数，表示a^b mod p的值。

数据范围
0≤a,b≤109
1≤p≤109
输入样例：
3 2 7
输出样例：
2
*/


long long a, b, p;

int main()
{
	cin >> a >> b >> p;
	long long ans = 1%p;
	while (b > 0) {
		if (b & 1) { ans *= a; ans %= p; }
		b >>= 1;
		a *= a; a %= p;
	}
	cout << ans << endl;
	return 0;
}



